Selection Sort - O(N^2) - Segments List to Parts¶
This algorithm Segments the List into two parts: Sorted and Unsorted.
We continuously remove the smallest element of the Unsorted Segment of the List
and APPEND it to the Sorted Segment.
Explanation:
In practice, we don’t need to create a new list for the sorted elements,
what we do is treat the leftmost part of the list as the Sorted Segment.
We then search the entire list for the smallest element, and swap it with the first element.
Now we know that the first element of the list is sorted,
we get the smallest element of the remaining items and swap it with the second element.
This iterates until the last item of the list is remaining element to be examined.
Note :
The Selection Sort improves on the Bubble Sort by making only one exchange
for every pass through the List.
Sample Data:
[4, 10, 8, 12, 6, 14, 2, 16, 1]
Expected Result:
[1, 2, 4, 6, 8, 10, 12, 14, 16]
def selectionSort(L):
# This value of i corresponds to how many values were sorted
for i in range(len(L)):
lowest_value_index = i
# This loop iterates over the unsorted items
for j in range(i + 1, len(L)):
if L[j] < L[lowest_value_index]:
lowest_value_index = j
# Swap values of the lowest unsorted element
# with the first unsorted element
L[i], L[lowest_value_index] = L[lowest_value_index], L[i]
print(L)
def selectionSort2(L):
# This value of i corresponds to how many values were not sorted
for i in range(len(L) - 1, 0, -1):
largest_value_index = 0
# This loop iterates over the unsorted items
for j in range(1, i + 1):
if L[j] > L[largest_value_index]:
largest_value_index = j
# Swap values of the largest unsorted element
# with the first unsorted element
L[i], L[largest_value_index] = L[largest_value_index], L[i]
print(L)
Test:
LON = [4, 10, 8, 12, 6, 14, 2, 16, 1]
selectionSort(LON)
Output:
[1, 10, 8, 12, 6, 14, 2, 16, 4]
[1, 2, 8, 12, 6, 14, 10, 16, 4]
[1, 2, 4, 12, 6, 14, 10, 16, 8]
[1, 2, 4, 6, 12, 14, 10, 16, 8]
[1, 2, 4, 6, 8, 14, 10, 16, 12]
[1, 2, 4, 6, 8, 10, 14, 16, 12]
[1, 2, 4, 6, 8, 10, 12, 16, 14]
[1, 2, 4, 6, 8, 10, 12, 14, 16]
[1, 2, 4, 6, 8, 10, 12, 14, 16]
[1, 2, 4, 6, 8, 10, 12, 14, 16]
Test:
LON = [4, 10, 8, 12, 6, 14, 2, 16, 1]
selectionSort2(LON)
Output:
[4, 10, 8, 12, 6, 14, 2, 1, 16]
[4, 10, 8, 12, 6, 1, 2, 14, 16]
[4, 10, 8, 2, 6, 1, 12, 14, 16]
[4, 1, 8, 2, 6, 10, 12, 14, 16]
[4, 1, 6, 2, 8, 10, 12, 14, 16]
[4, 1, 2, 6, 8, 10, 12, 14, 16]
[2, 1, 4, 6, 8, 10, 12, 14, 16]
[1, 2, 4, 6, 8, 10, 12, 14, 16]
[1, 2, 4, 6, 8, 10, 12, 14, 16]